﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AdvancedCollections.TreeHelper
{
    public class BinaryTreeNode<T>
    {
        public BinaryTreeNode(BinaryTreeNode<T> parent, IComparer<T> comparer)
        {
            Parent = parent;
            IsEmpty = true;
            Comparer = comparer;
        }

        public T Data { get; protected set; }

        public bool IsEmpty { get; protected set; }

        public BinaryTreeNode<T> LeftChild { get; protected set; }

        public BinaryTreeNode<T> Parent { get; protected set; }

        public BinaryTreeNode<T> RightChild { get; protected set; }

        protected IComparer<T> Comparer { get; private set; }

        public virtual bool Add(T item)
        {
            var node = FindNodeOrPlace(this, item);

            if (!node.IsEmpty)
                return false;
            else
            {
                node.FillNode(item);
                return true;
            }
        }

        public virtual bool Contains(T item)
        {
            var node = FindNodeOrPlace(this, item);

            return !node.IsEmpty;
        }

        public virtual bool Remove(T item, ref BinaryTreeNode<T> root)
        {
            var node = FindNodeOrPlace(this, item);

            if (node.IsEmpty)
                return false;
            else
            {
                if (node == root)
                {
                    root = node.RemoveNodeAndReturnSuccessor();
                    root.Parent = null;
                }
                else
                    node.RemoveNodeAndReturnSuccessor();
                return true;
            }
        }

        protected virtual void EmptyNode()
        {
            IsEmpty = true;
            Data = default(T);
            LeftChild = null;
            RightChild = null;
        }

        protected virtual void FillNode(T data)
        {
            IsEmpty = false;
            Data = data;
            InitializeEmptyChildren();
        }

        protected virtual BinaryTreeNode<T> FindNodeOrPlace(BinaryTreeNode<T> current, T item)
        {
            while (true)
            {
                if (current.IsEmpty)
                    return current;

                int comp = Comparer.Compare(item, current.Data);

                if (comp < 0)
                {
                    current = current.LeftChild;
                }
                else if (comp > 0)
                {
                    current = current.RightChild;
                }
                else
                    return current;
            }
        }

        protected virtual BinaryTreeNode<T> GetRightMostChild()
        {
            var current = this;

            while (!current.RightChild.IsEmpty)
                current = current.RightChild;

            return current;
        }

        protected virtual void InitializeEmptyChildren()
        {
            LeftChild = new BinaryTreeNode<T>(this, Comparer);
            RightChild = new BinaryTreeNode<T>(this, Comparer);
        }

        protected virtual BinaryTreeNode<T> RemoveNodeAndReturnSuccessor()
        {
            if (LeftChild.IsEmpty || RightChild.IsEmpty)
            {
                if (LeftChild.IsEmpty && RightChild.IsEmpty)
                {
                    EmptyNode();
                    return this;
                }
                else
                {
                    var successor = (LeftChild.IsEmpty ? RightChild : LeftChild);

                    if (Parent != null)
                        Parent.SwitchSuccessor(this, successor);

                    return successor;
                }
            }
            else
            {
                var rightMostChild = LeftChild.GetRightMostChild();

                rightMostChild.RightChild = RightChild;
                RightChild.Parent = rightMostChild;

                if (Parent != null)
                    Parent.SwitchSuccessor(this, LeftChild);

                return LeftChild;
            }
        }

        protected virtual void SwitchSuccessor(BinaryTreeNode<T> oldSuccessor, BinaryTreeNode<T> newSuccessor)
        {
            if (LeftChild == oldSuccessor)
                LeftChild = newSuccessor;
            else
                RightChild = newSuccessor;

            newSuccessor.Parent = this;
        }
    }
}